package company.qianxing_F;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Qi1 {

    //private static int  = 0;

    private static int minP = Integer.MAX_VALUE;

    private static int[] p;

    private static int[] w;

    private static int n;

    private static Map<String, Integer> dp = new HashMap<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuffer sb = new StringBuffer();
        int money = sc.nextInt();
        n = sc.nextInt();
        //价格
        p = new int[n];
        //价值
        w = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = sc.nextInt();
            w[i] = sc.nextInt();
            minP = Math.min(p[i], minP);
            sb.append("0");
        }
        System.out.println(helper(money, 0, sb));
    }

    private static int helper(int money, int value, StringBuffer use) {
        int maxValue = 0;
        if (dp.containsKey(use.toString()))
            return dp.get(use.toString());
        if (money < minP) {
            return value;
        }
        for (int i = 0; i < n; i++) {
            if (p[i] <= money) {
                StringBuffer copy = new StringBuffer(use);
                copy.setCharAt(i, (char) (copy.charAt(i) + 1));
                int tmp = helper(money - p[i], value + w[i], copy);
                dp.put(copy.toString(), tmp);
                maxValue = Math.max(maxValue, tmp);
            }
        }
        return maxValue;
    }
}
